\documentclass[12pt,a4paper,oneside,final]{book}
\usepackage[utf8]{inputenc}
\usepackage[IL2]{fontenc}
\usepackage[czech]{babel}
%\usepackage{mathptmx}
\usepackage{longtable}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{amsfonts}
\usepackage{hyperref}


\theoremstyle{plain}
\newtheorem{veta}{Věta}[section]
\newtheorem{lemma}[veta]{Lemma}

\theoremstyle{definition}
\newtheorem{definice}[veta]{Definice}
\newtheorem{pozn}[veta]{Poznámka}


\begin{document}
\chapter*{Úvod}
\addcontentsline{toc}{chapter}{Úvod}
V dnešní době moderní matematiky převládá snaha zkoumat problémy v co možná nejobecnější formě. Zvlášť obory, jako je algebra, kombinatorika, nebo teoretická informatika jsou vystavěny na abstraktních pojmech a definicích a člověk potom jen těžko pozná, na jaké konkrétní problémy se daná teorie vztahuje, nebo jaké má aplikace. Tento problém se však netýká pouze přímého využití v praxi. Velice často se zjišťuje, že dva pojmy, které spolu nemají zdánlivě mnoho společného, dávají dohromady velice zajímavé a důležité výsledky, kterých by se jinak dosahovalo velice složitě. Jedním s těchto případů je využití relace dobré předuspořádání v teorii formálních jazyků. 

Jedním z hlavních problémů zkoumaných v teorii formální jazyků je otázka, za jakých podmínek je daný jazyk regulární. Regulární jazyk je definován jako množina popsaná nějakým regulárním výrazem, regulární gramatikou nebo konečným automatem. Spojitost těchto pojmů se vysvětluje v základních kurzech formálních jazyků\cite{1}. Ukazuje se tak výhoda, kterou je zkoumaní jednoho pojmu pomocí různých přístupů. Regulární jazyky mají mnoho zajimavých vlastností, jako je například uzavřenost na množinové booleovské operace, zřetězení, Kleeneho hvězdičku nebo homomorfismy. Co se však může zdát jako složitý problém, má mnohdy jednoduché řešení při využití jiného přístupu. 

Jedním ze základních výsledků formálních jazyků je Nerodova věta, která popisuje regulární jazyky jako množiny vyplněné třídami nějaké kongruence (monotónní ekvivalence) konečného indexu. Tento výsledek je vlastě snaha o algebraický popis faktu, že je daný jazyk rozpoznáván konečným automatem. Třídy ekvivalentních slov totiž odpovídají stavům daného automatu. Tento výsledek se dá ovšem zobecnit a místo relace ekvivalence se uvažuje obecnější relace předuspořádání. Ukazuje se, že v případě předuspořádání se podmínka na konečnost dá nahradit slabší podmínkou, aby předuspořádání bylo dobré\cite{2}. 

Dalším z formalismů studovaných teorií formálních jazyků jsou přepisovací systémy, anglicky někdy označované jako semi-Thue systems. Ty indukují na množině všech slov předuspořádání a nabízí proto otázka, za jakých podmínek je toto předuspořádání dobré. V takových případech jsou jazyky uzavřené na tento přepisovací systém regulární. Ukážeme si několik tříd přepisovacích systémů, které tuto podmínku splňují.

Na závěr této práce si ukážeme, jak se dájí popsané výsledky využít při řešení nerovnic, ve kterých jsou konstanty i proměnné jazyky. V této části budemepřevážně čerpat z \cite{3}.


\chapter{Připomenutí pojmů}

\begin{definice}
\label{monotonie}
  Nechť $\Sigma$ je abeceda a $\rho$ binární relace na množině $\Sigma^*$.
  Řekneme, že $\rho$ je \emph{monotónní}, pokud pro každé $x_1, x_2, y_1, y_2 \in \Sigma^*$ platí:
  \[x_1 \: \rho \: y_1, \: x_2 \: \rho \: y_2   \Rightarrow x_1 x_2 \: \rho \: y_1 y_2       \]
  Řekneme, že $\rho$ je zprava (zleva) \emph{monotónní}, pokud pro každé $x_1, x_2, y \in \Sigma^*$ platí:
   \[x_1 \: \rho \: x_2,  \Rightarrow x_1 y \: \rho \: x_2 y \;\;\; (y x_1 \: \rho \: y x_2)      \]
  Relace ekvivalence $\sim$ na množine $\Sigma^*$, která je (zprava) monotónní se nazývá (pravá) \emph{kongruence}.
\end{definice}   

Následující věta jinak známá jako Nerodova dává základní algebraickou charakterizaci regulárních jazyků.

\begin{veta}
\label{nerode}
  Nechť $L\subseteq\Sigma^*$. Potom $L$ je regulární právě tehdy, když je sjednocením některých tříd pravé kongruence na $\Sigma^*$ konečného indexu.
\end{veta}

  Abychom na základě předchozího tvrzení mohli o některém jazyku $L$ tvrdit, že je regulární,
  stačí nám nalézt vhodnou kongruenci konečného indexu a ukázat, že daný jazyk je vyplněn některými
  třídami ekvivalence. Pokud bychom však chtěli tvrdit opak, tedy že $L$ není regulární, stáli bychom před nelehkým úkolem.
  Museli bychom ukázat, že žádná kongruence požadovaných vlastností neexistuje.  
  Tento problém řeší silnější tvrzení, tzv. Myhill-Nerodova věta, která se opírá o pojem kontextu.

\begin{definice}
\label{kontext}
  Nechť $L\subseteq\Sigma^*$ je jazyk (ne nutně regulární). Potom pro libovolné $x\in\Sigma^*$ definujme množinu \emph{kontextů} prvku $x$ v jazyce $L$ takto:
  \[C_L(x)=\{(y,z)\mid y,z \in \Sigma^*, yxz \in L\}.\]
Dále definujme pravý a levý kontext (prefix, suffix) následovně:
  \[C_L^r(x)=\{y \in \Sigma^*, xy \in L\},\]
  \[C_L^l(x)=\{y \in \Sigma^*, yx \in L\}.\]
Na základě pravého kontextu můžeme nyní zadefinovat relaci $\sim_L^r$ :
  \[x\sim_L^r y  \Longleftrightarrow C_L^r(x) = C_L^r(y).\]
\end{definice}  

Relaci $\sim_L^r$ se říká \emph{pravá syntaktická ekvivalence} a je zřejmé, že jde o pravou kongruenci.
Relace $\sim_L^r$ má tu vlastnost, že pro libovolný jazyk $L$ platí, že je sjednocením některých
tříd $\Sigma^*/_{\sim_L^r}$. 

\begin{lemma}
Nechť $L\subseteq\Sigma^*$. Potom $L$ je sjednocením některých tříd rozkladu  $\Sigma^*/_{\sim_L^r}$.
\end{lemma}

\begin{proof}
Chceme dokázat, že pro libovolné $x \in \Sigma^*$ patří třída $[x]_{\sim_L^r}$ buď celá do $L$, nebo s ním má prázdný průnik. Nechť tedy $y$ je libovolné slovo takové, že $x\sim_L^r y$. Potom podle definice relace $\sim_L^r$ platí  $C_L^r(x) = C_L^r(y)$, neboli $xz\in L \Longleftrightarrow yz\in L$. Zvolme tedy $z=\epsilon$ a dostaneme $x \in L \Longleftrightarrow y \in L$.
\end{proof}

Další zajímavou vlastností je, že každá pravá kongruence, pro kterou platí, že je jazyk
$L$ sjednocením jejích tříd ekvivalence, je zjemněním relace $\sim_L^r$. Je tedy ze všech takových kongruencí největší.
Tato vlastnost je formálně shrnuta v následujícím lemmatu. 

\begin{lemma}
  Nechť $L\subseteq\Sigma^*$ a $\sim$ je libovolná pravá kongruence na množině $\Sigma^*$ taková, že $L$ je sjednocením některých tříd rozkladu. Potom platí, že $\sim ~\subseteq ~ \sim_L^r$. 
\end{lemma}
\begin{proof}
Dokážeme, že pro libovolná slova $x, y$ taková, že platí $x \sim y$ , platí také $x \sim_L^r y$. Relace $\sim$ je pravá kongruence, a proto platí  $xz \sim yz$ pro libovolné $z \in \Sigma^*$.
Protože $L$ je sjednocením některých tříd ekvivalence  $\sim$, platí $xz \in L \Longleftrightarrow yz \in L$. Tento vztah platí pro libovolné $z$, z toho vyplývá rovnost $C_L^r(x)=C_L^r(y)$ a tedy $x \sim_L^r y$.

\end{proof}

Z Nerodovy věty a předchozího tvrzení už přímo plyne Myhill-Nerodova věta.
 
\begin{veta}
\label{Myhill-Nerode}
  Nechť $L\subseteq\Sigma^*$. Potom jsou následující tvrzení ekvivalentní:
  \begin{enumerate}
    \item[(i)] L je regulární jazyk.
    \item[(ii)] Relace $\sim_L^r$ má konečný index.
  \end{enumerate}
\end{veta} 



Myhill-Nerodova věta je tedy podstatně silnější. Říká nám přesně na kterou
z pravých kongruencí se máme zaměřit. Navíc v případě, že má tato kongruence nekonečný 
index, nemůže být zkoumaný jazyk regulární. 

Předchozí věta nám dává nutnou i postačující
podmínku regularity jazyka a tedy úplnou charakterizaci. Zjistit, zda je
konkrétní jazyk regulární lze však více způsoby. Například sestrojením konečného automatu rozpoznávajícího daný jazyk, nebo pomocí
uzávěrových vlastností. My se zaměříme na některá zobecnění Myhill-Nerodovy věty.

\begin{thebibliography}{10}
\addcontentsline{toc}{chapter}{\bibname}


\bibitem{1}
I. Černá, M. Křetínský, A. Kučera, \textit{Automaty a formální jazyky I}, 
FI MU, učební text k předmětu IB005,  2002, \url{http://is.muni.cz/do/1499/el/estud/fi/js06/ib005/Formalni_jazyky_a_automaty_I.pdf}

\bibitem{2}
W.~Bucherl, A. Ehrenfeucht, D. Haussler \textit{On total regulators generated by derivation relations}, Theoretical Computer Science, Amsterdam: Elsevier, 1985, roč. 40, s. 131-148. ISSN 0304-3975.


\bibitem{3}
Kunc M., \textit{Regular solutions of language inequalities and well quasi-orders}, Theoretical Computer Science, Amsterdam: Elsevier, 2005, roč. 348, 2-3, s. 277-293. ISSN 0304-3975.

\end{thebibliography}

\end{document}




